/**
 * @Author Stringzhua
 * @Date 2024/5/31 12:44
 * description:
 */

import java.util.*;

public class GrammarAnalysis {
    private static final char EPSILON = 'ε';
    private static final char DOLLAR_SIGN = '$';
    private static final int MAX_RULES = 100;
    private static final int MAX_NONTERMINALS = 10;
    private static final int MAX_TERMINALS = 10;
    private static final int MAX_INPUT_LENGTH = 100;

    private static String[] rules = new String[MAX_RULES];
    private static int numRules = 0;
    private static String[] nonTerminals = new String[MAX_NONTERMINALS];
    private static int numNonTerminals = 0;
    private static String[] terminals = new String[MAX_TERMINALS];
    private static int numTerminals = 0;
    private static int[][] parseTable = new int[MAX_NONTERMINALS][MAX_TERMINALS];

    public static void main(String[] args) {
        // 初始化文法规则和终结符、非终结符集合
        initialize();

        // 构造预测分析表
        constructParseTable();

        // 输出预测分析表
        printParseTable();

        // 分析输入序列id+id*id
        String input = "id+id*id";
        analyze(input);
    }

    private static void initialize() {
        // 添加文法规则
        addRule("E", "E+T");
        addRule("E", "T");
        addRule("T", "T*F");
        addRule("T", "F");
        addRule("F", "(E)");
        addRule("F", "id");

        // 添加终结符和非终结符集合
        addTerminal("+");
        addTerminal("*");
        addTerminal("(");
        addTerminal(")");
        addTerminal("id");
        addNonTerminal("E");
        addNonTerminal("T");
        addNonTerminal("F");
    }

    private static void addRule(String left, String right) {
        rules[numRules++] = left + "->" + right;
    }

    private static void addTerminal(String terminal) {
        terminals[numTerminals++] = terminal;
    }

    private static void addNonTerminal(String nonTerminal) {
        nonTerminals[numNonTerminals++] = nonTerminal;
    }

    private static void constructParseTable() {
        // 初始化预测分析表为-1（表示未定义）
        for (int i = 0; i < numNonTerminals; i++) {
            for (int j = 0; j < numTerminals; j++) {
                parseTable[i][j] = -1;
            }
        }

        // 对于每个产生式 A -> α，将 M[A, a] 置为产生式编号 k
        for (int i = 0; i < numRules; i++) {
            String[] parts = rules[i].split("->");
            String left = parts[0];
            String right = parts[1];
            int nonTerminalIndex = findNonTerminalIndex(left);
            int terminalIndex = findTerminalIndex(right.charAt(0));
            if (nonTerminalIndex != -1 && terminalIndex != -1) {
                parseTable[nonTerminalIndex][terminalIndex] = i;
            }
        }
    }

    private static int findNonTerminalIndex(String nonTerminal) {
        for (int i = 0; i < numNonTerminals; i++) {
            if (nonTerminals[i].equals(nonTerminal)) {
                return i;
            }
        }
        return -1;
    }

    private static int findTerminalIndex(char terminal) {
        for (int i = 0; i < numTerminals; i++) {
            if (terminals[i].charAt(0) == terminal) {
                return i;
            }
        }
        return -1;
    }

    private static void printParseTable() {
        System.out.println("Predictive Parsing Table:");
        System.out.print("\t");
        for (int i = 0; i < numTerminals; i++) {
            System.out.print(terminals[i] + "\t");
        }
        System.out.println();
        for (int i = 0; i < numNonTerminals; i++) {
            System.out.print(nonTerminals[i] + "\t");
            for (int j = 0; j < numTerminals; j++) {
                if (parseTable[i][j] == -1) {
                    System.out.print("-\t");
                } else {
                    System.out.print(rules[parseTable[i][j]] + "\t");
                }
            }
            System.out.println();
        }
    }

    private static void analyze(String input) {
        Stack<Character> stack = new Stack<>();
        stack.push(DOLLAR_SIGN); // 栈底符号为$
        stack.push('E'); // 栈顶符号为开始符号S
        int ip = 0; // 输入指针指向第一个终结符
        int top = 1; // 栈顶指针指向S
        while (true) {
            char x = stack.peek(); // 栈顶符号x
            char a = input.charAt(ip); // 输入符号a
            if (isTerminal(x)) { // 如果x是终结符
                if (x == a) { // 如果x等于a，弹出x，移动输入指针
                    stack.pop();
                    ip++;
                } else { // 否则报错
                    System.out.println("Error: Unmatched terminal symbol");
                    break;
                }
            } else { // 如果x是非终结符
                int ruleIndex = parseTable[findNonTerminalIndex(String.valueOf(x))][findTerminalIndex(a)]; // 查找M[x,a]对应的产生式编号
                if (ruleIndex == -1) { // 如果找不到对应的产生式，报错
                    System.out.println("Error: Undefined production");
                    break;
                } else { // 否则弹出x，压入Y1Y2...Yk（注意顺序）
                    stack.pop();
                    String[] parts = rules[ruleIndex].split("->");
                    String right = parts[1];
                    for (int i = right.length() - 1; i >= 0; i--) {
                        stack.push(right.charAt(i));
                    }
                }
            }
            if (x == DOLLAR_SIGN) { // 如果x为$，分析成功结束
                System.out.println("Successfully analyzed the input sequence");
                break;
            }
        }
    }

    private static boolean isTerminal(char c) {
        for (int i = 0; i < numTerminals; i++) {
            if (terminals[i].charAt(0) == c) {
                return true;
            }
        }
        return false;
    }
}
